The study of recently admixed populations provides unique tools for understanding recent population dynamics, socio-cultural factors associated with the founding of emerging populations, and the genetic basis of disease by means of admixture mapping. Historical records and recent autosomal data indicate that the South African Coloured population forms a unique highly admixed population, resulting from the encounter of different peoples from Africa, Europe, and Asia. However, little is known about the mode by which this admixed population was recently founded. Here we show, through detailed phylogeographic analyses of mitochondrial DNA and Y-chromosome variation in a large sample of South African Coloured individuals, that this population derives from at least five different parental populations (Khoisan, Bantus, Europeans, Indians, and Southeast Asians), who have differently contributed to the foundation of the South African Coloured. In addition, our analyses reveal extraordinarily unbalanced gender-specific contributions of the various population genetic components, the most striking being the massive maternal contribution of Khoisan peoples (more than 60%) and the almost negligible maternal contribution of Europeans with respect to their paternal counterparts. The overall picture of gender-biased admixture depicted in this study indicates that the modern South African Coloured population results mainly from the early encounter of European and African males with autochthonous Khoisan females of the Cape of Good Hope around 350 years ago.